package com.lsa.letcode.the104.maxDepthBt;

import java.util.ArrayDeque;
import java.util.Deque;

import com.lsa.letcode.common.TreeNode;

/**
 * Definition for a binary tree node. public class TreeNode { int val; TreeNode
 * left; TreeNode right; TreeNode(int x) { val = x; } }
 */
public class Solution {
	public int maxDepth(TreeNode root) {
		return maxDepthIter(root);
	}
	
	public int maxDepthIter(TreeNode r) {
		class StackFrame{
    		int step; // 0 - left, 1 - visit, 2 - right, 3 - return
    		TreeNode root;
    		int maxDepth;
			StackFrame(TreeNode root) {
				this.root = root;
			}
    	}
		
		Deque<StackFrame> stack = new ArrayDeque<StackFrame>();
		stack.add(new StackFrame(r));
		
		int retVal = -1;
		
		while(!stack.isEmpty()) {
    		StackFrame f = stack.peek();
    		if (f.root == null){
    			retVal = 0;
    			stack.pop();
    		}
    		else {
    			int step = f.step++;
    			switch (step) {
    			case 0:
    				stack.push(new StackFrame(f.root.left));
    				break;
    			case 1:
    				f.maxDepth = retVal;
    				stack.push(new StackFrame(f.root.right));
    				break;
    			case 2:
    				retVal = 1 + Math.max(f.maxDepth, retVal);
    				stack.pop();
    				break;
    			}
    		}
    	}
		
		return retVal;
	}
	
	public int maxDepthRec(TreeNode root) {
		if (root == null) {
			return 0;
		} else {
			return 1 + Math.max(maxDepthRec(root.left), maxDepthRec(root.right));
		}
	}
}